package class21To30;

public class ReversePairs {

    public static int MAXN = 100001;

    public static int[] help = new int[MAXN];

    public static int n;

    public int reversePairs(int[] nums) {
        return countPairs(nums, 0, n - 1);
    }

    private int countPairs(int[] nums, int l, int r) {
        if (l == r) {
            return 0;
        }
        int m = (l + r) / 2;
        return merge(nums, l, m, r) + countPairs(nums, m + 1, r) + countPairs(nums, l, m);
    }

    private int merge(int[] arr, int l, int m, int r) {
        int ans = 0;
        for (int i = l, j = m + 1; i <= m; i++) {
            // 防止整型溢出
            while (j <= r && (long) arr[i] > (long) arr[j] * 2) {
                j++;
            }
            ans += j - m - 1;
        }
        // 正常merge
        int k = l;
        int left = l;
        int right = m + 1;
        while (left <= m && right <= r) {
            help[k++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
        }
        while (left <= m) {
            help[k++] = arr[left++];
        }
        while (right <= r) {
            help[k++] = arr[right++];
        }
        for (k = l; k <= r; k++) {
            arr[k] = help[k];
        }
        return ans;
    }
}
